【解题报告】洛谷P1896 [SOCI2005]互不侵犯

题目描述

在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。

注：数据有加强（2018/4/25）

输入格式

只有一行，包含两个数N，K （ 1 <=N <=9, 0 <= K <= N * N）

输出格式

所得的方案数

输入输出样例

输入 #1

1
3 2

输出 #1

1
16

思路

互不侵犯是一道非常经典的 状态压缩Dp的题目（最主要我最近在练习状态压缩DP）

为什么不能用搜索呢，因为状态数量太多了，是一个指数级别的大爆搜，肯定不能过，而且，这个棋盘的某个格子放不放棋子是两个状态，0不放，1放，因此我们可以使用一个十进制数来表示一个二进制数，而二进制数又是一串数字，正好是由0和1组成的一个串，在看N≤9N\leq 9，因此存的下，所以我们用一个二进制数来表示每一行的状态，然而有一些状态是无用的，我们可以预处理一下（想一想，为什么）

预处理好每一行的状态之后，我们继续处理相邻两行之间的状态，处理方式和处理一行的时候的方式是一样的，我们都需要使用位运算，处理完之后，我们可以写出一个状态转移方程
f[i+1][w+king[now]][stnow]+=f[i][w][stformer](w+king[now]≤k) f[i+1][w+king[now]][st_{now}]+=f[i][w][st_{former}] (w+king[now]\leq k)
其中f[i][j][k]f[i][j][k]表示到了第i行，第i行及以前已经有j个国王了，当前第i行的状态为k（一个二进制数）

所以我们就可以开始动态规划了，时间复杂度很高，但是已经足以把这道题目过掉了

这道题非常重要，强烈建议读者独自写出代码

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
const int maxn=11;
int n,k;
bool st[1<<maxn];
bool dst[1<<maxn][1<<maxn];
int king[1<<maxn];
long long f[maxn][100][1<<maxn];
int main()
{
	cin>>n>>k;
	for(int i=0;i<(1<<n);i++)
	{
		if(i&(i>>1)) continue;
		st[i]=true;
		for(int j=1;j<=i;j<<=1)
		if(j&i)
		king[i]++;
	}
	for(int i=0;i<(1<<n);i++)
	{
		if(st[i]) 
		{
			for(int j=0;j<(1<<n);j++)
			{
				if(st[j]&&!(i&j)&&!(i&(j<<1))&&!(i&(j>>1)))
				dst[i][j]=true;
			}
		}
	}
	for(int i=0;i<(1<<n);i++)
	{
		if(st[i])
		f[1][king[i]][i]=1;
	}
	for(int i=1;i<n;i++)
	{
		for(int poss=0;poss<(1<<n);poss++)
		{
			if(st[poss])
			{
				for(int next=0;next<(1<<n);next++)
				{
					if(st[next]&&dst[poss][next])
					{
						for(int w=king[poss];w+king[next]<=k;w++)
						{
							f[i+1][w+king[next]][next]+=f[i][w][poss];
						}
					}
				}
			}
		}
	}
	long long ans=0;
	for(int i=0;i<(1<<n);i++)
	ans+=f[n][k][i];
	cout<<ans<<endl;
	return 0;
}